from copy import deepcopy
class Solution:
    def __init__(self):
        self.res = []

    def solveNQueens(self, n):
        board = [['.'] * n for _ in range(n)]
        row = 0
        self.backtrack(board, row)
        return self.res

    def backtrack(self, board, row):
        if row == len(board):
            re = []
            for ls in board:
                re.append("".join(ls))
            self.res.append(deepcopy(re))
            return
        n = len(board[row])
        for col in range(n):
            if not self.isvalid(board, row, col):
                continue
            board[row][col] = 'Q'
            self.backtrack(board, row + 1)
            board[row][col] = '.'

    # def isvalid(self,board,row,col):
    #   n = len(board)
    #  for i in range(row):
    #     for j in range(n):
    #        if (board[i][j] == 'Q') and (j == col or abs(i-row) == abs(j-col)):
    #           return False
    # return True
    def isvalid(self, board, row, col):
        n = len(board)
        for i in range(n):
            if board[i][col] == 'Q':
                return False
            i, j = row - 1, col + 1
            while i >= 0 and j < n:
                if board[i][j] == 'Q':
                    return False
                i, j = i - 1, j + 1

            i, j = row - 1, col - 1
            while i >= 0 and j >= 0:
                if board[i][j] == 'Q':
                    return False
                i, j = i - 1, j - 1
        return True

s = Solution()
print(s.solveNQueens(8))